package com.fosss.sort;

import java.time.Instant;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.Arrays;
import java.util.Date;

public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {8, 5, 6, 9, 1, 4};
//        System.out.println("排序前数组->" + Arrays.toString(arr));
//        quickSort(arr, 0, arr.length - 1);
//        System.out.println("排序后数组->" + Arrays.toString(arr));

        //测试时间复杂度
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        long startTime = System.currentTimeMillis();
        quickSort(arr,0, arr.length-1);
        long endTime = System.currentTimeMillis();
        System.out.println("花费的时间为"+(endTime-startTime)+"毫秒");//18
    }

    public static void quickSort(int[] arr, int left, int right) {

        if (left < right) {
            int key = arr[left];//基准数
            int l = left;
            int r = right;
            while (l < r) {

                /**
                 * 注意！！基准数从最左开始时，一定要先从右开始判断，否则出错
                 * 因为默认的基准数是在最左边，所以首先从右边开始比较进入while循环的判断条件
                 */
                while (arr[r] > key && l < r) {//找到中间数右边小于中间数的值,需要保证每次循环l<r
                    r--;
                }

                if (l < r) {//说明以上循环是没能满足arr[r]>middle而退出的
                    arr[l] = arr[r];
                    l++;
                }

                while (arr[l] < key && l < r) {//找到中间数左边的大于中间数的值,需要保证每次循环l<r
                    l++;
                }

                if (l < r) {//说明以上循环是没能满足arr[l]<middle而退出的
                    //进行赋值并移动
                    arr[r] = arr[l];
                    r--;
                }
            }

            //退出循环时l=r,将key赋值给该位置
            arr[l] = key;

            //向左递归
            quickSort(arr, left, r - 1);
            //向右递归
            quickSort(arr, l + 1, right);
        }

    }
}











